class Solution
{
public:
    // 复杂度 n^2 的暴力解，最后一个用例超时
    int findValidSplit(vector<int> &nums)
    {
        int n = nums.size();
        int bound = n - 1;
        while (bound > 0)
        {
            if (gcd(nums[0], nums[bound]) == 1)
            {
                --bound;
            }
            else
            {
                break;
            }
        }
        if (bound == n - 1)
        {
            return -1;
        }

        for (int i = 1; i <= bound; ++i)
        {
            for (int j = n - 1; j > bound; --j)
            {
                if (gcd(nums[i], nums[j]) != 1)
                {
                    bound = j;
                    break;
                }
            }
            if (bound >= n - 1)
            {
                return -1;
            }
        }
        return bound;
    }
};